package hzk.codex2016.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Trees {

	/**
	 * build a tree
	 * 
	 * @param vals
	 *            -1 means nothing
	 * @return the tree root
	 */
	public static TreeNode from(int... vals) {
		if (vals == null || vals.length == 0)
			return null;
		TreeNode[] nodes = new TreeNode[vals.length];
		nodes[0] = new TreeNode(vals[0]);
		int dad;
		for (int i = 1; i < vals.length; i++) {
			if (vals[i] == -1)
				continue;
			nodes[i] = new TreeNode(vals[i]);
			dad = (i - 1) / 2;
			if (nodes[dad] == null)
				continue;
			if ((i + 1) % 2 == 0) {
				nodes[dad].left = nodes[i];
			} else {
				nodes[dad].right = nodes[i];
			}

		}

		return nodes[0];

	}

	public static int count(TreeNode root) {
		if (root == null)
			return 0;
		return count(root.left) + count(root.right) + 1;

	}

	public static int[] to(TreeNode root) {
		class NInfo {
			TreeNode node;
			int index;

			NInfo(TreeNode node, int index) {
				this.node = node;
				this.index = index;
			}
		}
		int h = height(root);
		int n = (2 << h) + 1;
		int[] ret = new int[n];
		for (int i = 0; i < n; i++)
			ret[i] = -1;
		Stack<NInfo> st = new Stack<>();

		st.push(new NInfo(root, 0));
		NInfo ni;
		while (!st.empty()) {
			ni = st.pop();
			if (ni.node == null)
				continue;
			ret[ni.index] = ni.node.val;
			st.push(new NInfo(ni.node.left, ni.index * 2 + 1));
			st.push(new NInfo(ni.node.right, ni.index * 2 + 2));
		}
		return ret;
	}

	public static int height(TreeNode root) {
		if (root == null)
			return 0;
		return Math.max(height(root.left), height(root.right)) + 1;
	}

	private static void prtSp(int n) {
		while (n-- > 0)
			System.out.print(" ");
	}

	public static void print(TreeNode root) {
		int H = height(root);
		int lm = 0; // left margin
		for (int x = 0; x < H - 1; x++)
			lm = lm * 2 + 2;

		int[] vals = to(root);
		int len = vals.length;
		for (int h = 0, c = 1, k = 0; h < H; h++, c *= 2) {
			prtSp(lm);
			for (int i = 0; i < c; i++) {
				if (vals[k + i] >= 0)
					System.out.printf("%02d", vals[k + i]);
				else
					prtSp(2);
				prtSp(2 * lm + 2);
			}

			System.out.println();
			int p = lm - 1, q = 2, r = lm * 2;
			for (int i = 0; i < lm / 2; i++) {
				prtSp(p--);
				for (int j = 0; j < c; j++) {
					int son = 2 * (k + j) + 1;
					boolean lt = son < len && vals[son] >= 0;
					boolean rt = son + 1 < len && vals[son + 1] >= 0;
					if (lt)
						System.out.print("/");
					else
						prtSp(1);
					prtSp(q);
					if (rt)
						System.out.print("\\");
					else
						prtSp(1);
					prtSp(r);

				}
				System.out.println();
				q += 2;
				r -= 2;

			}
			k += c;
			lm = (lm - 2) / 2;

		}
		System.out.println();
	}

	public static void main(String[] args) {
		// int[] a = { 0, 1, 2, 3, 4, 5, 6 };
		int[] a = { 0, 1, 2, 3, 4, 5, 6, 7, -1, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
		TreeNode tn = from(a);
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(to(tn)));
		print(tn);
	}
}
